/*
 * Copyright (c) 2015, EURECOM (www.eurecom.fr)
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * The views and conclusions contained in the software and documentation are those
 * of the authors and should not be interpreted as representing official policies,
 * either expressed or implied, of the FreeBSD Project.
 */

#include "internal.h"/****************************************************************************/voidtest_lfds611_freelist (  void) {  printf ("\n"          "Freelist Tests\n"          "==============\n");  freelist_test_internal_popping ();  freelist_test_internal_pushing ();  freelist_test_internal_popping_and_pushing ();  freelist_test_internal_rapid_popping_and_pushing ();  return;}/****************************************************************************/voidfreelist_test_internal_popping (  void) {  unsigned int  loop,  cpu_count;  lfds611_atom_t  count = 0;  thread_state_t  *thread_handles;  enum lfds611_data_structure_validity  dvs = LFDS611_VALIDITY_VALID;  struct lfds611_freelist_state    *fs;  struct lfds611_freelist_element    *fe;  struct freelist_test_popping_state    *ftps;  unsigned int  *found_count;  /*     TRD : we create a freelist with 1,000,000 elements     the creation function runs in a single thread and creates     and pushes those elements onto the freelist     each element contains a void pointer which is its element number     we then run one thread per CPU     where each thread loops, popping as quickly as possible     each popped element is pushed onto a thread-local freelist     the threads run till the source freelist is empty     we then check the thread-local freelists     we should find we have every element     then tidy up  */  internal_display_test_name ("Popping");  cpu_count = abstraction_cpu_count ();  lfds611_freelist_new (&fs, 1000000, freelist_test_internal_popping_init, &count);  ftps = malloc (sizeof (struct freelist_test_popping_state) * cpu_count);  for (loop = 0; loop < cpu_count; loop++) {    (ftps + loop)->fs = fs;    lfds611_freelist_new (&(ftps + loop)->fs_thread_local, 0, NULL, NULL);  }  thread_handles = malloc (sizeof (thread_state_t) * cpu_count);  for (loop = 0; loop < cpu_count; loop++)    abstraction_thread_start (&thread_handles[loop], loop, freelist_test_internal_thread_popping, ftps + loop);  for (loop = 0; loop < cpu_count; loop++)    abstraction_thread_wait (thread_handles[loop]);  free (thread_handles);       // TRD : now we check the thread-local freelists  found_count = malloc (sizeof (unsigned int) * 1000000);  for (loop = 0; loop < 1000000; loop++)    *(found_count + loop) = 0;  for (loop = 0; loop < cpu_count; loop++) {    while (lfds611_freelist_pop ((ftps + loop)->fs_thread_local, &fe)) {      lfds611_freelist_get_user_data_from_element (fe, (void **)&count);      (*(found_count + count))++;      lfds611_freelist_push (fs, fe);    }  }  for (loop = 0; loop < 1000000 and dvs == LFDS611_VALIDITY_VALID; loop++) {    if (*(found_count + loop) == 0)      dvs = LFDS611_VALIDITY_INVALID_MISSING_ELEMENTS;    if (*(found_count + loop) > 1)      dvs = LFDS611_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;  }  // TRD : cleanup  free (found_count);  for (loop = 0; loop < cpu_count; loop++)    lfds611_freelist_delete ((ftps + loop)->fs_thread_local, NULL, NULL);  free (ftps);  lfds611_freelist_delete (fs, NULL, NULL);  // TRD : print the test result  internal_display_test_result (1, "freelist", dvs);  return;}/****************************************************************************/#pragma warning( disable : 4100 )intfreelist_test_internal_popping_init (  void **user_data,  void *user_state) {  lfds611_atom_t  *count;  assert (user_data != NULL);  assert (user_state != NULL);  count = (lfds611_atom_t *) user_state;  *(lfds611_atom_t *) user_data = (*count)++;  return (1);}#pragma warning( default : 4100 )/****************************************************************************/thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping (void *freelist_test_popping_state) {  struct freelist_test_popping_state    *ftps;  struct lfds611_freelist_element    *fe;  assert (freelist_test_popping_state != NULL);  ftps = (struct freelist_test_popping_state *)freelist_test_popping_state;  lfds611_freelist_use (ftps->fs);  lfds611_freelist_use (ftps->fs_thread_local);  while (lfds611_freelist_pop (ftps->fs, &fe))    lfds611_freelist_push (ftps->fs_thread_local, fe);  return ((thread_return_t) EXIT_SUCCESS);}/****************************************************************************/voidfreelist_test_internal_pushing (  void) {  unsigned int  loop,  cpu_count;  lfds611_atom_t  count = 0;  thread_state_t  *thread_handles;  enum lfds611_data_structure_validity  dvs;  struct freelist_test_pushing_state    *ftps;  struct lfds611_freelist_element    *fe;  struct lfds611_freelist_state    *fs,    *cleanup_fs;  struct freelist_test_counter_and_thread_number    *cnt,    *counter_and_number_trackers;  struct lfds611_validation_info    vi;  /*     TRD : we create an empty freelist, which we will push to     we then create one freelist per CPU, where this freelist     contains 100,000 elements per thread and     each element is an incrementing counter and unique ID     (from 0 to number of CPUs)     we then start one thread per CPU, where each thread is     given one of the populated freelists and pops from that     to push to the empty freelist     the reason for this is to achieve memory pre-allocation     which allows the pushing threads to run at maximum speed     the threads end when their freelists are empty     we then fully pop the now populated main freelist (onto     a second freelist, so we can cleanly free all memory),     checking that the counts increment on a per unique ID basis     and that the number of elements we pop equals 1,000,000 per thread     (since each element has an incrementing counter which is     unique on a per unique ID basis, we can know we didn't lose     any elements)  */  internal_display_test_name ("Pushing");  cpu_count = abstraction_cpu_count ();  ftps = malloc (sizeof (struct freelist_test_pushing_state) * cpu_count);  lfds611_freelist_new (&fs, 0, NULL, NULL);  for (loop = 0; loop < cpu_count; loop++) {    (ftps + loop)->thread_number = (lfds611_atom_t) loop;    // TRD : note count is shared across threads, so thread 0 is 0-100000, thread 1 is 100000-200000, etc    (ftps + loop)->count = &count;    lfds611_freelist_new (&(ftps + loop)->source_fs, 100000, freelist_test_internal_pushing_init, (void *)(ftps + loop));    (ftps + loop)->fs = fs;  }  thread_handles = malloc (sizeof (thread_state_t) * cpu_count);  for (loop = 0; loop < cpu_count; loop++)    abstraction_thread_start (&thread_handles[loop], loop, freelist_test_internal_thread_pushing, ftps + loop);  for (loop = 0; loop < cpu_count; loop++)    abstraction_thread_wait (thread_handles[loop]);  free (thread_handles);  // TRD : now fully pop and verify the main freelist  lfds611_freelist_new (&cleanup_fs, 0, NULL, NULL);  counter_and_number_trackers = malloc (sizeof (struct freelist_test_counter_and_thread_number) * cpu_count);  for (loop = 0; loop < cpu_count; loop++) {    (counter_and_number_trackers + loop)->counter = 100000 * loop;    (counter_and_number_trackers + loop)->thread_number = (lfds611_atom_t) loop;  }  vi.min_elements = vi.max_elements = 100000 * cpu_count;  lfds611_freelist_query (fs, LFDS611_FREELIST_QUERY_VALIDATE, &vi, (void *)&dvs);  while (dvs == LFDS611_VALIDITY_VALID and lfds611_freelist_pop (fs, &fe)) {    lfds611_freelist_get_user_data_from_element (fe, (void **)&cnt);    if (cnt->counter != (counter_and_number_trackers + cnt->thread_number)->counter++)      dvs = LFDS611_VALIDITY_INVALID_MISSING_ELEMENTS;    lfds611_freelist_push (cleanup_fs, fe);  }  // TRD : clean up  free (counter_and_number_trackers);  for (loop = 0; loop < cpu_count; loop++)    lfds611_freelist_delete ((ftps + loop)->source_fs, NULL, NULL);  free (ftps);  lfds611_freelist_delete (cleanup_fs, freelist_test_internal_pushing_delete, NULL);  lfds611_freelist_delete (fs, NULL, NULL);  // TRD : print the test result  internal_display_test_result (1, "freelist", dvs);  return;}/****************************************************************************/intfreelist_test_internal_pushing_init (  void **user_data,  void *user_state) {  struct freelist_test_counter_and_thread_number    *ftcatn;  struct freelist_test_pushing_state    *ftps;  assert (user_data != NULL);  // TRD : user_state is being used as an integer type  *user_data = malloc (sizeof (struct freelist_test_counter_and_thread_number));  ftps = (struct freelist_test_pushing_state *)user_state;  ftcatn = (struct freelist_test_counter_and_thread_number *)*user_data;  ftcatn->counter = (*ftps->count)++;  ftcatn->thread_number = ftps->thread_number;  return (1);}/****************************************************************************/#pragma warning( disable : 4100 )voidfreelist_test_internal_pushing_delete (  void *user_data,  void *user_state) {  assert (user_data != NULL);  assert (user_state == NULL);  free (user_data);  return;}#pragma warning( default : 4100 )/****************************************************************************/thread_return_t CALLING_CONVENTION freelist_test_internal_thread_pushing (void *freelist_test_pushing_state) {  struct freelist_test_pushing_state    *ftps;  struct lfds611_freelist_element    *fe;  assert (freelist_test_pushing_state != NULL);  ftps = (struct freelist_test_pushing_state *)freelist_test_pushing_state;  lfds611_freelist_use (ftps->source_fs);  lfds611_freelist_use (ftps->fs);  while (lfds611_freelist_pop (ftps->source_fs, &fe))    lfds611_freelist_push (ftps->fs, fe);  return ((thread_return_t) EXIT_SUCCESS);}/****************************************************************************/voidfreelist_test_internal_popping_and_pushing (  void) {  unsigned int  loop,  cpu_count;  thread_state_t  *thread_handles;  enum lfds611_data_structure_validity  dvs;  struct lfds611_freelist_state    *fs;  struct freelist_test_popping_and_pushing_state    *pps;  struct lfds611_validation_info    vi;  /*     TRD : we have two threads per CPU     the threads loop for ten seconds     the first thread pushes 100000 elements then pops 100000 elements     the second thread pops 100000 elements then pushes 100000 elements     all pushes and pops go onto the single main freelist     after time is up, all threads push what they have remaining onto     the main freelist     we then validate the main freelist  */  internal_display_test_name ("Popping and pushing (10 seconds)");  cpu_count = abstraction_cpu_count ();  lfds611_freelist_new (&fs, 100000 * cpu_count, NULL, NULL);  pps = malloc (sizeof (struct freelist_test_popping_and_pushing_state) * cpu_count * 2);  for (loop = 0; loop < cpu_count; loop++) {    (pps + loop)->fs = fs;    lfds611_freelist_new (&(pps + loop)->local_fs, 0, NULL, NULL);    (pps + loop + cpu_count)->fs = fs;    lfds611_freelist_new (&(pps + loop + cpu_count)->local_fs, 100000, NULL, NULL);  }  thread_handles = malloc (sizeof (thread_state_t) * cpu_count * 2);  for (loop = 0; loop < cpu_count; loop++) {    abstraction_thread_start (&thread_handles[loop], loop, freelist_test_internal_thread_popping_and_pushing_start_popping, pps + loop);    abstraction_thread_start (&thread_handles[loop + cpu_count], loop, freelist_test_internal_thread_popping_and_pushing_start_pushing, pps + loop + cpu_count);  }  for (loop = 0; loop < cpu_count * 2; loop++)    abstraction_thread_wait (thread_handles[loop]);  free (thread_handles);  for (loop = 0; loop < cpu_count * 2; loop++)    lfds611_freelist_delete ((pps + loop)->local_fs, NULL, NULL);  free (pps);  vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;  lfds611_freelist_query (fs, LFDS611_FREELIST_QUERY_VALIDATE, (void *)&vi, (void *)&dvs);  lfds611_freelist_delete (fs, NULL, NULL);  // TRD : print the test result  internal_display_test_result (1, "freelist", dvs);  return;}/****************************************************************************/thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_popping (void *freelist_test_popping_and_pushing_state) {  struct freelist_test_popping_and_pushing_state    *pps;  struct lfds611_freelist_element    *fe;  time_t  start_time;  unsigned int  count;  assert (freelist_test_popping_and_pushing_state != NULL);  pps = (struct freelist_test_popping_and_pushing_state *)freelist_test_popping_and_pushing_state;  lfds611_freelist_use (pps->fs);  lfds611_freelist_use (pps->local_fs);  time (&start_time);  while (time (NULL) < start_time + 10) {    count = 0;    while (count < 100000) {      lfds611_freelist_pop (pps->fs, &fe);      if (fe != NULL) {        lfds611_freelist_push (pps->local_fs, fe);        count++;      }    }    while (lfds611_freelist_pop (pps->local_fs, &fe))      lfds611_freelist_push (pps->fs, fe);  }  return ((thread_return_t) EXIT_SUCCESS);}/****************************************************************************/thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_pushing (void *freelist_test_popping_and_pushing_state) {  struct freelist_test_popping_and_pushing_state    *pps;  struct lfds611_freelist_element    *fe;  time_t  start_time;  unsigned int  count;  assert (freelist_test_popping_and_pushing_state != NULL);  pps = (struct freelist_test_popping_and_pushing_state *)freelist_test_popping_and_pushing_state;  lfds611_freelist_use (pps->fs);  lfds611_freelist_use (pps->local_fs);  time (&start_time);  while (time (NULL) < start_time + 10) {    while (lfds611_freelist_pop (pps->local_fs, &fe))      lfds611_freelist_push (pps->fs, fe);    count = 0;    while (count < 1000) {      lfds611_freelist_pop (pps->fs, &fe);      if (fe != NULL) {        lfds611_freelist_push (pps->local_fs, fe);        count++;      }    }  }  // TRD : now push whatever we have in our local freelist  while (lfds611_freelist_pop (pps->local_fs, &fe))    lfds611_freelist_push (pps->fs, fe);  return ((thread_return_t) EXIT_SUCCESS);}/****************************************************************************/voidfreelist_test_internal_rapid_popping_and_pushing (  void) {  unsigned int  loop,  cpu_count;  thread_state_t  *thread_handles;  struct lfds611_freelist_state    *fs;  struct lfds611_validation_info    vi;  enum lfds611_data_structure_validity  dvs;  /*     TRD : in these tests there is a fundamental antagonism between     how much checking/memory clean up that we do and the     likelyhood of collisions between threads in their lock-free     operations     the lock-free operations are very quick; if we do anything     much at all between operations, we greatly reduce the chance     of threads colliding     so we have some tests which do enough checking/clean up that     they can tell the freelist is valid and don't leak memory     and here, this test now is one of those which does minimal     checking - in fact, the nature of the test is that you can't     do any real checking - but goes very quickly     what we do is create a small freelist and then run one thread     per CPU, where each thread simply pops and then immediately     pushes     the test runs for ten seconds     after the test is done, the only check we do is to traverse     the freelist, checking for loops and ensuring the number of     elements is correct  */  internal_display_test_name ("Rapid popping and pushing (10 seconds)");  cpu_count = abstraction_cpu_count ();  lfds611_freelist_new (&fs, cpu_count, NULL, NULL);  thread_handles = malloc (sizeof (thread_state_t) * cpu_count);  for (loop = 0; loop < cpu_count; loop++)    abstraction_thread_start (&thread_handles[loop], loop, freelist_test_internal_thread_rapid_popping_and_pushing, fs);  for (loop = 0; loop < cpu_count; loop++)    abstraction_thread_wait (thread_handles[loop]);  free (thread_handles);  vi.min_elements = cpu_count;  vi.max_elements = cpu_count;  lfds611_freelist_query (fs, LFDS611_FREELIST_QUERY_VALIDATE, (void *)&vi, (void *)&dvs);  lfds611_freelist_delete (fs, NULL, NULL);  // TRD : print the test result  internal_display_test_result (1, "freelist", dvs);  return;}/****************************************************************************/thread_return_t CALLING_CONVENTION freelist_test_internal_thread_rapid_popping_and_pushing (void *lfds611_freelist_state) {  struct lfds611_freelist_state    *fs;  struct lfds611_freelist_element    *fe;  time_t  start_time;  assert (lfds611_freelist_state != NULL);  fs = (struct lfds611_freelist_state *)lfds611_freelist_state;  lfds611_freelist_use (fs);  time (&start_time);  while (time (NULL) < start_time + 10) {    lfds611_freelist_pop (fs, &fe);    lfds611_freelist_push (fs, fe);  }  return ((thread_return_t) EXIT_SUCCESS);}
